#include "LinkList.h"


//创建一个节点
LinkNode *LinkNodeCreate(LinkListType value)
{
    LinkNode *new_node=(LinkNode *)malloc(sizeof(LinkNode));
    new_node->data=value;
    new_node->next=NULL;
    return new_node;
}
//销毁一个节点
void LinkNodeDestroy(LinkNode *to_delete)
{
    if(to_delete==NULL)
    {
        return;
    }
    free(to_delete);
    to_delete=NULL;
}
//打印链表中的元素
void PrintListChar(LinkNode *head,const char *msg)
{
    printf("\n%s\n",msg);
    printf("head: \n");
    if(head==NULL)
    {//链表为空
        return;
    }
    LinkNode *cur=head;
    while(cur!=NULL)
    {
        printf("[%c] ",cur->data);
        cur=cur->next;
    }
    printf("\n");
}
//链表的初始化
void LinkListInit(LinkNode **head)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    *head=NULL;
}
//链表的头插
LinkNode *LinkListPushFront(LinkNode **head,LinkListType value)
{
    if(head==NULL)
    {//参数错误
        return NULL;
    }
    LinkNode *new_node=LinkNodeCreate(value);
    if(*head==NULL)
    {
        *head=new_node;
        return new_node;
    }
    new_node->next=*head;
    (*head)=new_node;
    return new_node;
}
//链表的头删
void LinkListPopFront(LinkNode **head)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    if(*head==NULL)
    {//链表为空
        return;
    }
    LinkNode *to_delete=*head;
    *head=to_delete->next;
    LinkNodeDestroy(to_delete);
}
//链表的尾插
void LinkListPushBack(LinkNode **head,LinkListType value)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    LinkNode *new_node=LinkNodeCreate(value);
    if(*head==NULL)
    {//链表为空
        *head=new_node;
        return;
    }
    LinkNode *cur=*head;
    while(cur->next!=NULL)
    {
        cur=cur->next;
    }
    cur->next=new_node;
}
//链表的尾删
void LinkListPopBack(LinkNode **head)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    if(*head==NULL)
    {//链表为空
        return;
    }

    LinkNode *cur=*head;
    LinkNode *to_delete=*head;
    LinkNode *pre=NULL;
    while(cur->next!=NULL)
    {
        pre=cur;
        cur=cur->next;
    }
    //出循环cur就是要删除的元素
    if(pre==NULL)
    {//说链表只有一个节点
        *head=NULL;
        LinkNodeDestroy(to_delete);
        return;
    }
    else
    {
        to_delete=cur;
        pre->next=NULL;
        LinkNodeDestroy(to_delete);
    }
}
//查找元素在链表中的位置
LinkNode *LinkListFind(LinkNode *head,LinkListType to_find)
{
    if(head==NULL)
    {//链表为空 
        return NULL;
    }
    LinkNode *cur=head;
    while(cur!=NULL)
    {
        if(cur->data==to_find)
        {//找到了
            return cur;
        }
        cur=cur->next;
    }
    //出循环说明没有找到
    return NULL;
}
//在所给位置之前进行插入
void LinkListInsert(LinkNode **head,LinkNode *pos,LinkListType value)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    LinkNode *new_node=LinkNodeCreate(value);
    if(*head==NULL)
    {//链表为空
        *head=new_node;
        return;
    }
    if(pos==*head)
    {//要插入的位置就是第一个节点
        new_node->next=*head;
        *head=new_node;
        return;
    }
    LinkNode *cur=*head;
    while(cur!=NULL)
    {
        if(cur->next==pos)
        {//找到要插入的位置
            new_node->next=pos;
            cur->next=new_node;
            return;
        }
        cur=cur->next;
    }
    //出循环说明没有找到要插入的位置

}
//在所给位置之后进行插入
void LinkListInsertBack(LinkNode **head,LinkNode *pos,LinkListType value)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    LinkNode *new_node=LinkNodeCreate(value);
    if(*head==NULL)
    {//链表为空
        *head=new_node;
        return;
    }
    LinkNode *cur=*head;
    while(cur!=NULL)
    {
        if(cur->next==pos)
        {//找到要插入的位置
            new_node->next=pos->next;
            pos->next=new_node;
        }
        cur=cur->next;
    }
    //出循环说明没有找到要插入的位置
}
//删除指定位置的元素
void LinkListErase(LinkNode **head,LinkNode *pos)
{
    if(head==NULL||pos==NULL)
    {//参数错误
        return;
    }
    if(*head==NULL)
    {//链表为空
        return;
    }
    LinkNode *to_delete=*head;
    if(pos==*head)
    {//要删除的节=节点是第一个节点
        *head=(*head)->next;
        LinkNodeDestroy(to_delete);
        return;
    }   
    LinkNode *cur=*head;
    while(cur!=NULL)
    {
        if(cur->next==pos)
        {//找到要删除的节点
            to_delete=pos;
            cur->next=pos->next;
            LinkNodeDestroy(to_delete);
            return;
        }
        cur=cur->next;
    }
    //出循环说明没有找到要删除的节点
}
//删除指定位置的元素(时间复杂度尾O(1))
void LinkListErase_1(LinkNode **head,LinkNode *pos)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    if(*head==NULL)
    {//链表为空
        return;
    }
    if(pos->next==NULL)
    {//说明pos是最后一个节点,此处不做处理，不符合时间复杂度O(1)的要求
        return;
    }
    LinkNode *to_delete=pos->next;
    //删除采用移花接木的方法，并不是真正的删除pos
    pos->data=pos->next->data;//将pos->next的元素赋值给pos，然后再删除pos->next
    pos->next=to_delete->next;
    LinkNodeDestroy(to_delete);
}
//删除指定元素的节点
void LinkListRemove(LinkNode **head,LinkListType value)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    if(*head==NULL)
    {//链表为空
        return;
    }
    LinkNode *to_delete=*head;
    LinkNode *pre=NULL;
    if((*head)->data==value)
    {//说明要删除的节点是第一个节点
        to_delete=*head;
        *head=(*head)->next;
        LinkNodeDestroy(to_delete);
        return;
    }
    LinkNode *cur=*head;
    while(cur!=NULL)
    {
        if(cur->data==value)
        {//找到要删除的元素
            to_delete=cur;
            pre->next=cur->next;
            LinkNodeDestroy(to_delete);
            return;
        }
        pre=cur;
        cur=cur->next;
    }
    //出循环说明没有找到要删除的元素
}
//删除指定元素的节点（将所有该元素的节点都删除）
void _LinkListRemoveAll(LinkNode **start,LinkListType value)
{
    if(*start==NULL)
    {//说明已经删除完了
        return;
    }
    LinkNode *cur=*start;
    LinkNode *pre=NULL;
    if((*start)->data==value)
    {//说明要删除的是第一个节点
        (*start)=(*start)->next;
        LinkNodeDestroy(cur);
        _LinkListRemoveAll(start,value);
    }
    else
    {
        while(cur!=NULL)
        {
            if(cur->data==value)
            {
                pre->next=cur->next;
                LinkNodeDestroy(cur);
                _LinkListRemoveAll(&pre,value);
            }
            pre=cur;
            cur=cur->next;
        }
        //出循环说明没找到
        return;
    }
}
void LinkListRemoveAll(LinkNode **head,LinkListType value)
{
    if(head==NULL)
    {//参数错误
        return;
    }
    if(*head==NULL)
    {//链表为空 
        return;
    }
    _LinkListRemoveAll(head,value);
}
//链表的判空
int LinkListEmpty(LinkNode *head)
{
    if(head==NULL)
    {//链表为空
        return 1;
    }
    else
    {
        return 0;
    }
}
//求链表的大小
size_t LinkListSize(LinkNode *head)
{
    LinkNode *cur=head;
    size_t size=0;
    while(cur!=NULL)
    {
        size++;
        cur=cur->next;
    }
    return size;
}
//销毁链表
void LinkListDestroy(LinkNode **head)
{
    if(head==NULL)
    {//链表为空
        return;
    }
    LinkNode *cur=*head;
    LinkNode *to_delete=*head;
    while(cur!=NULL)
    {
        to_delete=cur;
        cur=cur->next;
        LinkNodeDestroy(to_delete);
    }
    *head=NULL;
}
